package leetcode.weekly.week335;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

//Solution3Test
public class Solution5 {

	public int findValidSplit(int[] nums) {
		Map<Integer, Integer> cnts = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			cnts.put(num, cnts.getOrDefault(num, 0) + 1);
			while (num % 2 == 0) {
				num /= 2;
				cnts.put(2, cnts.getOrDefault(2, 0) + 1);
			}
			for (int j = 3; j <= num && num > 1; j += 2) {
				while (num % j == 0) {
					num /= j;
					cnts.put(j, cnts.getOrDefault(j, 0) + 1);
				}
			}
		}
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < nums.length - 1; i++) {
			int num = nums[i];
			cnts.put(num, cnts.getOrDefault(num, 0) - 1);
			set.add(num);
			while (num % 2 == 0) {
				num /= 2;
				cnts.put(2, cnts.getOrDefault(2, 0) - 1);
				set.add(2);
			}
			for (int j = 3; j <= num && num > 1; j += 2) {
				while (num % j == 0) {
					num /= j;
					cnts.put(j, cnts.getOrDefault(j, 0) - 1);
					set.add(j);
				}
			}
			boolean flag = false;
			for (int p : set) {
				if (cnts.get(p) > 0) {
					flag = true;
				}
			}
			if (!flag) {
				return i;
			}
		}
		return -1;
	}

}
